package may;

import java.util.*;

/**
 * @author ：冯涛滔
 * @date ：Created in 2020-5-27 14:28
 * @description： 贪心算法
 * @modified By：
 * @version:
 */
public class May27 {
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/smallest-range-ii/ 最小差值2
     * 升序排序之后确保数组遍历到的值都是比较小的
     * 所以遍历到的值全部+K 剩下的意外就是最小值 到底回事 0+K 还是A[j]-k j就是指下一个位置的值
     * create time: 2020-5-27 14:29
     * @params [A, K]
     * @return int
     */
    public static int smallestRangeII(int[] A, int K) {
        if(A.length==1||A.length==0){
            return 0;
        }
        Arrays.sort(A);
        int ans = A[A.length-1] - A[0];
        int high = 0;
        int low = 0;
        for (int i = 0; i < A.length-1; i++) {
            int j = i+1;
            high = Math.max(A[A.length-1]-K, A[i]+K);
            low = Math.min(A[0]+K,A[j]-K);
            ans = Math.min(ans,high - low);
        }
        return ans;
    }
    public int minDominoRotations(int[] A, int[] B) {
        int[] hash = new int[7];
        hash[0] = 0;
        for(int i=0; i<A.length; i++){
            hash[ A[i] ] ++;
            hash[ B[i] ] ++;
        }

        int max = Integer.MIN_VALUE,target=0;
        for(int i=1;i<=6;i++){
            if(hash[i]>max){
                max = hash[i]; //出现的次数
                target = i; //记录是哪一个数字
            }
        }
        if(max<A.length) return -1;
        //若出现的次数小于数组的大小的话，则不可能做到

        // 开始翻转
        int cnt1=0;
        for(int i=0;i<A.length;i++){//假设 A 数组可以实现
            if(A[i] == target) continue;
            if(B[i] != target) return -1;
            else cnt1++;//统计需要翻转的次数
        }
        int cnt2=0;
        for(int i=0;i<B.length;i++){//假设 B 数组可以实现
            if(B[i] == target) continue;
            if(A[i] != target) return -1;
            else cnt2++;//统计需要翻转的次数
        }
        return Math.min(cnt1, cnt2);//返回较小者

    }
    public int maxProfit(int[] prices) {
        /**
         * create by: 冯涛滔
         * description: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/ 买卖股票二
         * 贪心策略 :每一回合都买和卖都进行一次 记录下最大的一个利润
         * create time: 2020-5-27 15:35
         * @params [prices]
         * @return int
         */
        int max = 0;
        for (int i = 1; i < prices.length; i++) {
            int temp = prices[i]-prices[i-1];
            if(temp>0) {
                max += temp;
            }
        }
        return max;
    }
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int j = 0;
        int count = 0;
        for (int i = 0; i < s.length; i++) {
            if(s[i]>=g[j]){//饼干够大分出去
                count++;
                j++;
            }
        }
        return count;
    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/play-with-chips/ 玩筹码
     * 重点 移动两格是不需要体力的
     * 所以我们可以不费体力地将筹码分成 奇数位置上的一组和偶数位置上的一组 挑筹码最少的一组移动一位就可以变成一堆了
     * create time: 2020-5-27 16:21
     * @params [chips]
     * @return int
     */
    public int minCostToMoveChips(int[] chips) {
        int oddNums=0,evenNums=0;
        for(int i=0;i<chips.length;i++){
            if(chips[i]%2==0){
                oddNums++;
            }else{
                evenNums++;
            }
        }
        return Math.min(oddNums,evenNums);
    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/minimum-subsequence-in-non-increasing-order/ 最小子序列
     * create time: 2020-5-27 16:44
     * @params [nums]
     * @return java.util.List<java.lang.Integer>
     */
    public static List<Integer> minSubsequence(int[] nums) {
        int sum = 0;
        int listSum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum+=nums[i];
        }
        List<Integer> list = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = nums.length-1; i >=0; i--) {
            list.add(nums[i]);
            sum-=nums[i];
            listSum+=nums[i];
            if(listSum>sum){
                break;
            }
        }
        return list;
    }
    public int twoCitySchedCost(int[][] costs) {
        //公司首先将这 2N 个人全都安排飞往 B 市，再选出 N 个人改变它们的行程，让他们飞往 A 市。如果选择改变一个人的行程，
        // 那么公司将会额外付出 price_A - price_B 的费用，这个费用可正可负
        // 因此最优的方案是，选出 price_A - price_B 最小的 N 个人，让他们飞往 A 市，其余人飞往 B 市。。
        Arrays.sort(costs, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o1[1] - (o2[0] - o2[1]); //主要是这里 按a地和b地的价格差排序
            }
        });

        int total = 0;
        int n = costs.length / 2;
        for (int i = 0; i < n; ++i){
            total += costs[i][0] + costs[i + n][1];
        }
        return total;
    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/wiggle-subsequence/ 摆动序列
     * 序列的差值是 正负 或者 负正 交叉出现的
     * 小大小大小 序列要这样排序所以就 进行一个先序排序 然后从两端开始遍历
     * create time: 2020-5-27 20:35
     * @params [nums]
     * @return int
     */
    public int wiggleMaxLength(int[] nums) {
        if (nums.length < 2)
            return nums.length;
        int prevdiff = nums[1] - nums[0];
        int count = prevdiff != 0 ? 2 : 1;
        for (int i = 2; i < nums.length; i++) {
            int diff = nums[i] - nums[i - 1];
            if ((diff > 0 && prevdiff <= 0)     || (diff < 0 && prevdiff >= 0)) {
                count++;
                prevdiff = diff;
            }
        }
        return count;
    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/broken-calculator/solution/pi-liao-de-ji-suan-qi-by-leetcode/ 坏了的计算器
     * 逆向思维 除了可以对x做乘二和减一 也对y做除二和加一 y一定要设置成偶数
     * create time: 2020-5-27 23:03
     * @params [X, Y]
     * @return int
     */
    public int brokenCalc(int X, int Y) {
        int res = 0;
        while(Y>X){
            if (Y % 2 == 1){
                Y++;

            }else{
                Y /= 2;
            }
            res++;
        }
        return res+X-Y;
    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/cinema-seat-allocation/ 电影院安排位置 超时了 可以采用二进制
     * create time: 2020-5-28 11:20
     * @params [n, reservedSeats]
     * @return int
     */
    public static int maxNumberOfFamilies(int n, int[][] reservedSeats) {
        int res = 0; //总数
        int j = 0;
        boolean[][] dp = new boolean[n+1][11];
        for (int i = 0; i < reservedSeats.length ; i++) {
            dp[reservedSeats[i][0]][reservedSeats[i][1]] = true;
        }
        for (int i = 1; i <= n ; i++) {
            boolean[] flag = new boolean[3];
            for (int k = 2; k < 6; k++) {
                if(dp[i][k]){
                    flag[0] = true;
                    break;
                }
            }
            for (int k = 6; k < 10; k++) {
                if(dp[i][k]){
                    flag[1] = true;
                    break;
                }
            }
            if(flag[0]&&flag[1]){
                for (int k = 4; k < 8; k++) {
                    if(dp[i][k]){
                        flag[2] = true;
                        break;
                    }
                }
            }else{
                flag[2] = true;
            }
            for (int k = 0; k < flag.length; k++) {
                if(!flag[k])res++;
            }
        }
        return res;
    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/gas-station/submissions/ 加油站
     * create time: 2020-5-28 11:36
     * @params [gas, cost]
     * @return int
     */
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int sum = 0;
        int total = 0;
        int start = 0;
        for(int i=0;i<gas.length;i++){
            total += (gas[i] - cost[i]);
            if(sum < 0){ //证明上一个位置是不能用的了 所以sum重置成当前下标 以及 start也重置
                sum = gas[i]-cost[i];
                start = i;
            }else{
                sum += (gas[i]-cost[i]);
            }
        }
        return total >= 0?start:-1;
    }
    public static void main(String[] args) {
        int[] list = {1,5,5,8,10,10,13,15,16,17};

        int[][] s = {{4,7},{4,1},{3,1},{5,9},{4,4},{3,7},{1,3},{5,5},{1,6},{1,8},{3,9},{2,9},{1,4},{1,9},{1,10}};
        maxNumberOfFamilies(5,s);
    }
}
